package com.smatiger.hotdeploy.loader.test;

/**
* @Description: 快速排序法
* @author smatiger
* @date 2017年6月28日 下午3:19:50 
*/
public class FastSort {

    public static void main(String[] args) {
        int[] array = { 6, 3, 8, 1, 9, 7, 321, 34, 231, 5432, 65, 234, 21, 3121 };
        array = fastSort(array, 0, array.length - 1);
        for (int num : array) {
            System.out.println(num);
        }
    }


    private static int[] fastSort(int[] array, int start, int end) {
        if (start < end) {
            int pos = partition(array, start, end);
            fastSort(array, start, pos - 1);
            fastSort(array, pos + 1, end);
        }
        return array;
    }

    private static int partition(int[] array, int start, int end) {
        int key = array[start];
        while (start < end) {
            while (start < end && array[end] >= key) {
                end--;
            }
            if (start < end) {// 0<3
                array[start] = array[end];// 138197
                start++;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            if (start < end) {// 2<3
                array[end] = array[start];//138897
                end--;
            }
            array[start] = key;//136897
        }
        return start;//2
    }

}
